package org.laizili.solution.leetcode;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

/**
 * <a href="https://leetcode.cn/problems/find-right-interval/">436. 寻找右区间</a>
 * <p>
 * tags: 排序+二分搜索; 排序+双指针; TreeMap简单应用
 */
public class Problem436 {
    private static class Solution {
        public int[] findRightInterval(int[][] intervals) {
            int[][] starts = new int[intervals.length][2];
            for (int i = 0; i < intervals.length; i++) {
                starts[i] = new int[]{intervals[i][0], i};
            }
            Arrays.sort(starts, Comparator.comparingInt(l -> l[0]));
            int[] res = new int[intervals.length];
            for (int i = 0; i < intervals.length; i++) {
                res[i] = upperBounds(starts, intervals[i][1]);
            }
            return res;
        }

        // find which start_j greater than or equal to end_i
        static int upperBounds(int[][] starts, int target) {
            int left = 0, right = starts.length - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (target == starts[mid][0]) {
                    return starts[mid][1];
                } else if (target < starts[mid][0]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            if (left < starts.length)
                return starts[left][1];
            else
                return -1;
        }
    }
    // TreeMap
    private static class Solution2 {
        public int[] findRightInterval(int[][] intervals) {
            int len = intervals.length;
            TreeMap<Integer, Integer> sortedMap = new TreeMap<>();
            for (int i = 0; i < len; i++) {
                sortedMap.put(intervals[i][0], i);
            }
            int[] res = new int[len];
            for (int i = 0; i < len; i++) {
                Map.Entry<Integer, Integer> ceilingEntry = sortedMap.ceilingEntry(intervals[i][1]);
                res[i] = ceilingEntry == null ? -1 : ceilingEntry.getValue();
            }
            return res;
        }
    }
    // 排序+双指针
    private static class Solution3 {
        public int[] findRightInterval(int[][] intervals) {
            int len = intervals.length;
            int[][] starts = new int[len][2];
            int[][] ends = new int[len][2];
            for (int i = 0; i < len; i++) {
                starts[i][0] = intervals[i][0];
                starts[i][1] = i;
                ends[i][0] = intervals[i][1];
                ends[i][1] = i;
            }
            Comparator<int[]> cmp = Comparator.comparingInt(v -> v[0]);
            Arrays.sort(starts, cmp);
            Arrays.sort(ends, cmp);
            int[] res = new int[len];
            for (int i = 0, j = 0; i < len; i++) {
                while (j < len && ends[i][0] > starts[j][0]) {
                    j++;
                }
                if (j < len) {
                    res[ends[i][1]] = starts[j][1];
                } else {
                    res[ends[i][1]] = -1;
                }
            }
            return res;
        }
    }

    public static void main(String[] args) {
        //[[1,2]]
//        int[][] arr = new int[][]{{1,2}};
        //[[3,4],[2,3],[1,2]]
//        int[][] arr = new int[][]{{3, 4}, {2, 3}, {1, 2}};
        // [[1,4],[2,3],[3,4]]
        int[][] arr = new int[][]{{1, 4}, {2, 3}, {3, 4}};
        System.out.println(Arrays.toString(new Solution().findRightInterval(arr)));
    }
}
